package com.acwing.partition4;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/1/17 10:32
 */
public class AC344观光之旅 {

    private static final int N = 110, M = 10010, INF = 0x3f3f3f3f;
    //middle[i][j]记录dist[i][j]经过的点
    private static int[][] graph = new int[N][N], dist = new int[N][N], middle = new int[N][N];
    private static int n = 0, m = 0, cnt = 0;

    //path记录当前结果所经过的点
    private static int[] path = new int[N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i++) Arrays.fill(graph[i], INF);
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split("\\s+");
            int u = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]), w = Integer.parseInt(s[2]);
            graph[u][v] = graph[v][u] = Math.min(graph[u][v], w);
        }
        int ans = floyd();
        if (ans == INF) writer.write("No solution.\n");
        else {
            //存在最小环，输出最小环
            for (int i = 0; i < cnt; i++) writer.write(path[i] + " ");
        }
        writer.flush();
    }

    private static int floyd() {
        int answer = INF;
        //复制graph到dist中
        for (int i = 1; i <= n; i++) System.arraycopy(graph[i], 1, dist[i], 1, n);
        for (int k = 1; k <= n; k++) {
            //当前节点的最大编号是k，这里只计算了从i到j的所有方案中，不经过k的情况。找最小环
            for (int i = 1; i + 1 < k; i++) {
                for (int j = i + 1; j < k; j++) {
                    if ((long) dist[i][j] + graph[i][k] + graph[k][j] < answer) {
                        //此时的dist数组保存的是上一轮的数据，此时的answer记录了从i->k->j的最小环长度，同时需要更新最小环的经过路径
                        answer = dist[i][j] + graph[i][k] + graph[k][j];
                        cnt = 0;
                        path[cnt++] = k;
                        path[cnt++] = i;
                        dfs(i, j);
                        path[cnt++] = j;
                    }
                }
            }
            //floyd加入统计从i到j所有经过k的方案
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        middle[i][j] = k;
                    }
                }
            }
        }
        return answer;
    }

    private static void dfs(int i, int j) {
        //如果i到j节点中间没有经过任何节点，搜索结束
        if (middle[i][j] == 0) return;
        //i->k->j，分治处理i->k部分和k->j部分
        int k = middle[i][j];
        dfs(i, k);
        path[cnt++] = k;
        dfs(k, j);
    }
}
